#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣3249. 统计好节点的数目
// 【难度】中等
// 【提交】2025.10.16 https://leetcode.cn/problems/count-the-number-of-good-nodes/submissions/671171480/
// 【标签】树；深度优先搜索；图
class Solution_LC3249 {
public:
    int countGoodNodes(vector<vector<int>>& edges) {
        int res = 0;
        vector<vector<int>> g(edges.size() + 1);
        for(auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        function<int(int, int)> dfs = [&](int n, int fa) -> int {
            bool valid = true;
            int total_size = 0;
            int subtree_size = 0;
            for(auto& child : g[n]) {
                if(child != fa) {
                    int size = dfs(child, n);
                    if(subtree_size == 0) {
                        subtree_size = size;
                    } else if(size != subtree_size) {
                        valid = false;
                    }
                    total_size += size;
                }
            }
            if(valid) res++;
            return total_size + 1;
        };
        dfs(0, -1);
        return res;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个无向树的边列表，统计树中"好节点"的数量。
 * 好节点定义：如果删除该节点后，剩下的所有连通分量的大小都相同，则该节点为好节点。
 * 模型：树形结构+深度优先搜索，通过计算子树大小来判断节点是否满足条件。
 * 
 * 二、标准解法状态设计
 * 1. 根据边列表构建树的邻接表表示。
 * 2. 使用深度优先搜索遍历树结构。
 * 3. 对于每个节点，递归计算所有子树的尺寸。
 * 4. 检查所有子树的尺寸是否相同，如果相同则标记为好节点。
 * 5. 返回当前子树的总大小（包括当前节点）。
 * 
 * 三、你的实现思路
 * 使用DFS遍历树，在递归过程中计算每个节点的子树大小。
 * 通过比较所有子树的尺寸是否相同来判断节点是否为好节点。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<vector<int>> g(edges.size() + 1); // 构建邻接表
 * for(auto& e : edges) { // 构建无向图
 *     g[e[0]].push_back(e[1]);
 *     g[e[1]].push_back(e[0]);
 * }
 * 
 * function<int(int, int)> dfs = [&](int n, int fa) -> int {
 *     bool valid = true; // 假设当前节点是好节点
 *     int total_size = 0; // 所有子树总大小
 *     int subtree_size = 0; // 用于比较的子树基准大小
 *     
 *     for(auto& child : g[n]) { // 遍历邻居
 *         if(child != fa) { // 排除父节点
 *             int size = dfs(child, n); // 递归计算子树大小
 *             if(subtree_size == 0) { // 第一个子树
 *                 subtree_size = size; // 设置基准大小
 *             } else if(size != subtree_size) { // 子树大小不一致
 *                 valid = false; // 不是好节点
 *             }
 *             total_size += size; // 累加子树大小
 *         }
 *     }
 *     
 *     if(valid) res++; // 如果是好节点，增加计数
 *     return total_size + 1; // 返回当前子树总大小（包括当前节点）
 * };
 * 
 * dfs(0, -1); // 从根节点开始DFS
 * return res; // 返回好节点总数
 * 
 * 五、正确性证明
 * 算法通过DFS遍历整棵树，对于每个节点：
 * 1. 计算所有子树的尺寸
 * 2. 检查所有子树尺寸是否相同
 * 3. 如果相同，则该节点删除后剩下的连通分量大小相同，符合好节点定义
 * 由于DFS会访问所有节点，且每个节点都进行了正确的判断，因此算法正确。
 * 
 * 六、复杂度
 * 时间：O(n)，每个节点只被访问一次。
 * 空间：O(n)，需要邻接表存储树结构，递归栈深度为树的高度。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法高效，只需一次DFS遍历；
 *   - 代码简洁，逻辑清晰；
 *   - 使用lambda表达式使代码更紧凑。
 * 缺点：
 *   - 递归深度可能受树高度限制；
 *   - 对于根节点的特殊情况可能需要额外考虑。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (edges.empty()) return 1; // 只有根节点
 * 2. 可以考虑使用迭代DFS避免递归深度问题；
 * 3. 对于根节点，删除后剩下的连通分量是各个子树，算法已正确处理；
 * 4. 对于叶子节点，没有子树，自动满足条件（valid保持为true）。
 * 
 * 九、一句话总结
 * 通过深度优先搜索计算子树大小并比较一致性，你的实现高效地统计了好节点数量，
 * 展现了树形结构问题中递归思想的巧妙应用。
 */